package com.剑指offer.第六章;

import java.util.Stack;

/**
 * 使用分治法进行求解
 * <p>
 * <p>
 * 还有一种使用 栈
 */
public class 直方图最大矩形面积 {

    public static int resolve(int[] nums) {
        return helper(nums, 0, nums.length);
    }

    public static int helper(int[] nums, int start, int end) {

        // 空数组
        if (start == end) {
            return 0;
        }

        // 数组大小为1
        if (start + 1 == end) {
            return nums[start];
        }

        // 一直找到 最小的长方形
        int minIndex = start;
        for (int i = start + 1; i < end; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }
        }

        int area = (end - start) * nums[minIndex];
        int left = helper(nums, start, minIndex);
        int right = helper(nums, minIndex + 1, end);

        int max = Math.max(area, left);

        return Math.max(max, right);
    }

    public static int resolve1(int[] nums) {

        Stack<Integer> stack = new Stack<>();

        stack.push(-1);


        int maxArea = 0;

        for (int i = 0; i < nums.length; i++) {
            /**
             * 以某根柱子为顶的最大矩形，一定是从该柱子向两侧延申直到遇到比它矮的柱子就停止，然后计算出两边比该这个柱子矮的矮的距离(也就是宽)
             */
            while (stack.peek() != -1 && nums[stack.peek()] >= nums[i]) {
                Integer pop = stack.pop();
                // 计算两个矮的柱子的距离
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, width * nums[pop]);
            }
            stack.push(i);
        }

        while (stack.peek() != -1) {
            int height = nums[stack.pop()];
            int width = nums.length - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }

        return maxArea;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 4, 5, 6, 1, 4, 2};
        System.out.println(resolve1(nums));

    }

}
